package ArrayProblems;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class searchMatrix {
    /**
     * 方法一：递归法
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        if (target < matrix[0][0]) {
            return false;
        }
        return isInPlace(matrix, target, 0, 0);
    }

    private boolean isInPlace(int[][] matrix, int target, int row, int col) {
        if (row >= matrix.length || col >= matrix[0].length || row < 0 || col < 0) {
            return false;
        }
        if (target == matrix[row][col]) {
            return true;
        } else if (target < matrix[row][col]) {
            return false;
        } else {
            return isInPlace(matrix, target, row + 1, col) || isInPlace(matrix, target, row, col + 1);
        }
    }
}

class searchMatrixI {
    public boolean searchMatrix(int[][] matrix, int target) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                queue.add(matrix[i][j]);
            }
        }
        return queue.contains(target);
    }
}

class searchMatrixII {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int row = 0, col = n - 1;
        while (row < m && col >= 0) {
            if (target == matrix[row][col]) return true;
            else if (target < matrix[row][col]) col--;
            else row++;
        }
        return false;
    }
}